|Title of the article||
UNRELIABILITY LOWER-BOUND ESTIMATE OF NONBRANCHING PROGRAMMES
Alekhina Marina Anatolyevna, Doctor of physical and mathematical sciences, professor, head of sub-department of discrete mathematics, Penza State University, email@example.com
The article considers a problem of synthesis of nobranching programs with conditional stop-operator. All functional operators are supposed to be subject to out-put inverse failures with probability ε (ε∈(0,1/2). Conditional stop-operators are absolutely reliable. Any boolean function f∈K (class K is found explicitly) is proved to be impossible to realize by irreducible nobranching program with unreliability of less than ε(1 – ε)m, where m – the number of functional operators in the program. These and the previous results on the upper bound for the unreliability of the nobranching programs prove that almost all functions can be realized by asymptotically optimal reliable nobranching programs that operate with unreliability asymptotically equal to ε at ε → 0.
boolean functions, nobranching programs, conditional stop-operator, synthesis, reliability
Дата обновления: 22.07.2014 11:40